The present invention relates to the transmission of messages on a digital network and, more particularly, to a method of multiplexing buffer space between the messages of backlogged flows at the output port of a switch.
The present invention addresses the problem of sharing buffer space between backlogged flows that pass through a link. Since the traffic of the flows may be bursty, the link is occasionally congested, and backlogged messages are queued up. The standard approach of storing the backlogged messages in a single queue is problematic, as it might lead to unfairness between the flows and jitter amplification within a flow. A common approach to resolve these problems is to maintain a queue for each flow and serve the queues in a Round-Robin manner. See, for example, John Nagle, "On packet switches with infinite storage", IEEE/ACM Transactions on Communication, 35(4): 435-438, April 1987 and S. Keshav, "A control-theoretic approach to flow control", in Proc. SIGCOMM, pp. 3-16, September 1991. This solves the fairness and jitter problems, but introduces a new problem, that of memory management.
Two basic approaches for this memory management are common, a static approach and a dynamic approach. In the static approach a queue is dedicated to each active flow while in the dynamic approach a linked-list is assigned to each flow. The former is inefficient in the usage of space but better suited for hardware implementation, while the latter is optimal in the usage of space but requires sophisticated hardware.
There is thus a widely recognized need for, and it would be highly advantageous to have, a method of memory management in flow control that combines the spatial efficiency of the dynamic approach with the relatively simple hardware of the static approach.